#include <string>
#include <iostream>
using namespace std;
// #define DEBUG
const int N = 8;

string OK
;
void Debug(string flag, string str, int pos)
{

    #ifdef DEBUG
        for(int i = 1; i <= pos; i++) printf("  ");
        printf("[%s][S -> %s][%d][%s]\r\n", flag.c_str(), str.c_str(), pos, OK.c_str());
    #endif
}

void change(int pos, string replacement)
{
    if (pos != std::string::npos) {
        // 调整字符串大小以容纳新字符
        OK.resize(OK.size() + replacement.size() - 1);
 
        // 替换字符（并自动处理后续字符的移动）
        OK.replace(pos, 1, replacement);
    }
}

bool match_a(string inp, int& pos)
{
    int cur = pos;
    Debug("Try", "a", cur);
    if(pos < inp.size() & inp[pos] == 'a')
    {
        Debug("Matched", "a",cur);
        pos++; return true;
    }
    Debug("NOT Matched", "a", cur);
    return false;
}

bool match_end(string inp, int& pos)
{
    int cur = pos;
    Debug("Try", "END", cur);
    if( pos == inp.size()) Debug("Matched", "END", cur);
    else Debug("NOT Matched", "END", cur);

    return pos == inp.size();
}

bool match_S(string inp, int& pos)
{
    int fallback = pos;
    string curstr = OK;
    // 尝试匹配"aSa"
    change(pos, "aSa");
    Debug("Try", "aSa", fallback);

    if (match_a(inp, pos) && match_S(inp, pos) && match_a(inp, pos)) {
        Debug("Matched", "aSa", fallback);
        return true;
    }
    Debug("NOT Matched", "aSa", fallback);
    OK = curstr;

    // aSa没匹配上 回到之前的位置 
    pos = fallback;
    
    // 尝试匹配"aa"
    change(pos, "aa");
    Debug("Try", "aa", fallback);
    if (match_a(inp, pos) && match_a(inp, pos)) {
        Debug("Matched", "aa", fallback);
        return true;
    }
    Debug("NOT Matched", "aa", fallback);
    OK = curstr;

    Debug("!!!S!!!NOT Matched", "任意展开都失败", fallback);
    
    return false;

}

bool match(string inp)
{
    int pos = 0;
    return match_S(inp, pos) && match_end(inp, pos);
}

int main()
{
    freopen("./out.txt","w",stdout);
    cout << "OPEN FINISH" << endl;

    for(int i = 1; i <= 33; i++)
    {
        // 形成字符串
        string s(i, 'a');
        #ifdef DEBUG
        printf("--------------------------BEGIN MATCH %s---------------------------\r\n", s.c_str());
        cout << endl;
        #endif
        
        bool result = match(s);

        cout << i << " " << (result ? "true" : "false") << endl;
        cout << endl;
    }

    return 0;
}